package org.lql.algo.codecrush.week009.question.type.IIII;

import org.lql.algo.common.TreeNode;

/**
 * @author: liangqinglong
 * @date: 2025-08-20 17:05
 * @description: 面试题 04.06. 后继者 <a href="https://leetcode.cn/problems/successor-lcci/description/">...</a>
 **/
public class InorderSuccessor {

	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
		return getNext(root, p.val);
	}

	public TreeNode getNext(TreeNode root, int val) {
		TreeNode ans = null;
		TreeNode curr = root;
		while (curr != null) {
			if (curr.val == val) {
				if (curr.right != null) {
					ans = curr.right;
					while(ans.left != null) {
						ans = ans.left;
					}
				}
				break;
			}
			if (val < curr.val) {
				if (ans == null || ans.val > curr.val) {
					ans = curr;
				}
				curr = curr.left;
			} else {
				curr = curr.right;
			}
		}
		return ans;
	}
}
